package cn.algorithms_4ed.algo.sort;

/**
 * Shell
 * <p/>
 * 统计显示，如果数组长度为N，
 * 平均比较次数为
 * 平均交换次数约为
 * <p/>
 * User: erhu
 * Date: 13-6-15
 * Time: 上午11:17
 */
public class Shell extends Sort {

    public static void main(String[] args) {
        Shell shell = new Shell();
        shell.sort().show();
    }

    @Override
    Sort sort() {
        int h = 1;
        while (h < data.length / 3) {
            h = h * 3 + 1;
        }
        while (h >= 1) {
            doSort(h);
            h /= 3;
        }
        return this;
    }

    private void doSort(int h) {
        for (int i = 1; i < data.length; i++) {
            final Comparable tmp = data[i];

            int j = i;
            for (; j >= h && less(tmp, data[j - h]); j -= h) {
                // 此处使用移位，比sort()中使用交换效率高；
                data[j] = data[j - h];
            }
            data[j] = tmp;
        }
    }
}
